package com.lsa.helpers;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.AbstractList;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

import com.lsa.helpers.SingleLinkedList.ListNode;

public class Utils
{
	public static List<Integer> randomList(int maxSize, int lower, int upper) {
		int size = Utils.random(1, maxSize);
		List<Integer> l = new ArrayList<>(size);
		for (int i = 0; i < size; i++) {
			l.add(Utils.random(lower, upper));
		}
		
		return l;
	}
	
	public static Pair<Integer,Integer> minMax(Collection<Integer> c) 
	{
		if (c.isEmpty()) {
			return Pair.create(null, null);
		}
		
		Integer min;
		Integer max;
		
		Iterator<Integer> iter = c.iterator();
		if (c.size() % 2 != 0) {
			min = max = iter.next();
		}
		else {
			min = Integer.MAX_VALUE;
			max = Integer.MIN_VALUE;
		}
		
		for (Iterator<Integer> iterator = iter; iterator.hasNext();) {
			Integer n1 = iterator.next();
			Integer n2 = iterator.next();
			
			Integer newMin;
			Integer newMax;
			
			if (n1 < n2) {
				newMin = n1;
				newMax = n2;
			}
			else {
				newMin = n2;
				newMax = n1;
			}
			
			if (min > newMin) {
				min = newMin;
			}
			if (max < newMax) {
				max = newMax;
			}
		}
		
		return Pair.create(min, max);
	}
	
	public static void print(Collection c)
	{
		for (Iterator iterator = c.iterator(); iterator.hasNext();)
		{
			System.out.println(iterator.next());
		}
	}
	
	public static void print(int[] arr)
	{
		if (arr == null)
		{
			System.out.println("null");
			return;
		}
		
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i]+" ");
		}
		
		System.out.println();
	}
	
	public static Collection asCollection(int[] array)
	{
		List l = new ArrayList();
		
		for (int i = 0; i < array.length; i++)
		{
			l.add(Integer.valueOf(array[i]));
		}
		
		return l;
	}
	
	public static Object[] asObjectArray(String[] strings)
	{
		Object[] arr =new Object[strings.length];
		for (int i = 0; i < strings.length; i++)
		{
			arr[i] = strings[i];
		}
		
		return arr;
	}
	
	public static void print(int[][] array2D)
	{
		for (int i = 0; i < array2D.length; i++) 
		{
			int[] row = array2D[i];
			for (int j = 0; j < array2D.length; j++) 
			{
				System.out.print(row[j]+" ");
			}
			
			System.out.println();
		}
	}
	
	public static void printMonospace(int[][] array2D, int spaceCount)
	{
		for (int i = 0; i < array2D.length; i++) 
		{
			int[] row = array2D[i];
			for (int j = 0; j < row.length; j++) 
			{
				System.out.print(String.format("%1$-"+spaceCount+"s", row[j]));
			}
			
			System.out.println();
		}
	}
	
	public static void swap(int[] array, int i, int j)
	{
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
	
	public static <T> void swap(T[] array, int i, int j){
		T t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
	
	public static void swap(List<Integer> list, int i, int j)
	{
		Integer t = list.get(i);
		list.set(i, list.get(j));
		list.set(j, t);
	}
	
	public static boolean isEmpty(int[] array)
	{
		return null == array || array.length == 0;
	}
	
	public static boolean isEmpty(List array)
	{
		return null == array || array.size() == 0;
	}
	
	public static int[][] createIntArray2D(int m, int n, int fill)
	{
		int[][] array2D = new int[m][n];
		
		for (int i = 0; i < array2D.length; i++) 
		{
			for (int j = 0; j < array2D[i].length; j++) 
			{
				array2D[i][j] = fill;
			}
		}
		
		return array2D;
	}
	
	public static int[][] createIntArray2D(int m, int n)
	{
		return createIntArray2D(m,n,0);
	}
	
	public static void print(List<Pair<Integer, Integer>> list)
	{
		for (Pair<Integer, Integer> pair : list)
		{
			String str = "";
			if (pair.getFirst() != null)
				str += pair.getFirst();
			
			str += ":";
			
			if (pair.getSecond() != null)
				str += pair.getSecond();
			
			System.out.println(str);
		}
	}
	
	public static  List<Pair<Integer, Integer>> createPairsByPairing(int[] arr)
	{
		List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
		
		for (int i = 0; i < arr.length; i++)
		{			
			Pair<Integer, Integer> p = new Pair<Integer, Integer>();
			p.setFirst(arr[i]);
			p.setSecond(arr[i]);
			
			l.add(p);
		}
		
		return l;
	}
	
	public static  List<Pair<Integer, Integer>> createPairsPutInFirst(int[] arr)
	{
		List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
		
		for (int i = 0; i < arr.length; i++)
		{			
			Pair<Integer, Integer> p = new Pair<Integer, Integer>();
			p.setFirst(arr[i]);
			l.add(p);
		}
		
		return l;
	}
	
	public static  List<Pair<Integer, Integer>> createPairsPutInSecond(int[] arr)
	{
		List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
		
		for (int i = 0; i < arr.length; i++)
		{			
			Pair<Integer, Integer> p = new Pair<Integer, Integer>();
			p.setSecond(arr[i]);
			l.add(p);
		}
		
		return l;
	}
	
	public static List<Integer> createIntegerListUniform(int from, int to, int step) {
		List<Integer> l = new ArrayList<Integer>();
		for (int i = from; i <= to; i+=step) {
			l.add(i);
		}
		return l;
	}
	
	/**
	 * Creates {@code int[]}   
	 * @param from - first element of the array
	 * @param to - right threshold, right element of the array <= of it
	 * @param step - difference between two consecutive elements
	 * @return array filled
	 */
	public static int[] createIntArray1D(int from, int to, int step) {
		List<Integer> l = createIntegerListUniform(from, to, step);
		int[] arr = new int[l.size()];
		for (int i = 0; i < l.size(); i++) {
			arr[i] = l.get(i);
		}
		return arr;
	}
	public static int[] create01IntArray1D(String data) {
		//1011100101
		int len = data.length();
		char[] chars = new char[2* len - 1];
		for (int i = 0; i < len - 1; i++) {
			chars[i*2] = data.charAt(i);
			chars[i*2 + 1] = ' ';
		}
		chars[chars.length - 1] = data.charAt(len - 1);
		return createIntArray1D(new String(chars));
	}
	
	public static int[] createIntArray1D(String data)
	{
		List<Integer> list = new ArrayList<Integer>();
		
		StringTokenizer st;
		
		if (data.indexOf(',') > -1)
		{
		    st = new StringTokenizer(data, ",");
		}
		else
		{
		    st = new StringTokenizer(data);
		}
		
		while(st.hasMoreTokens())
		{
			list.add(Integer.parseInt(TextUtils.trim(st.nextToken())));
		}
		
		int[] array = new int[list.size()];
		for (int i = 0; i < list.size(); i++)
		{
			array[i] = list.get(i);
		}
		
		return array;
	}
	
	/**
	 * @param data - in form of "1 2 3 5"
	 * @return
	 */
	public static SingleLinkedList<Integer> createSingleLinkedListOfInteger(String data) {
		SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
		int[] arr = createIntArray1D(data);
		for (int i = 0; i < arr.length; i++) {
			list.add(arr[i]);
		}
		return list;
	}
	
	/**
	 * @param data - in form of "1 2 3 5 1". If last int same as intermediate before -> cicle is formed
	 * @return
	 */
	public static SingleLinkedList<Integer> createSingleLinkedListWithCirculars(String data) {
		SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
		int[] arr = createIntArray1D(data);
		Map<Integer, ListNode<Integer>> data2Node = new HashMap<Integer, SingleLinkedList.ListNode<Integer>>();
		for (int i = 0; i < arr.length - 1; i++) {
			int n = arr[i];
			ListNode<Integer> node = list.add(n);
			data2Node.put(n, node);
		}
		
		int last = arr[arr.length - 1];
		list.getTail().next = data2Node.get(last);
		return list;
	}
	
	/**
	 * $PRE:{8 9 1 12 1 2 5 8 9 4}
	 * movePart 1 1  
	 * 8 9 1 12 1 2 5 8 9 4
	 * =>
	 * 8 9 9 1 12 1 2 5 8 9
	 * 
	 * movePart 1 4
	 * 8 9 1 12 1 2 5 8  9 4
	 * 8 9 1 12 1 9 1 12 1 2 
	 * 
	 * movePart 0 1
	 * 8 9 1 12 1 2 5 8 9 4
	 * 8 8 9 1 12 1 2 5 8 9  
	 * @param array
	 * @param i
	 * @param partSize
	 * @param step
	 * @return
	 */
	public static int[] moveSlice(int[] array, int i, int step)
	{
		int sourceIdx = array.length - 1 - step;
		int destIdx = array.length - 1;
		
		for ( ; sourceIdx > i - 1; )
		{
			array[destIdx--] = array[sourceIdx--];
		}
		
		return array;
	}
	
	/**
	 * $PRE:{8 9 1 7 1 2 5 8 9 4}
	 * 
	 * moveElement 3 1
	 * 0 1 2 3 4 5 6 7 8 9
	 * 8 9 1 7 1 2 5 8 9 4
	 * 8 7 9 1 1 2 5 8 9 4
	 * 
	 * moveElement 1 7
	 * 0 1 2 3 4 5 6 7 8 9
	 * 8 9 1 7 1 2 5 8 9 4
	 * 8 1 7 1 2 5 8 9 9 4
	 * 
	 * moveElement 3 4
	 * 0 1 2 3 4 5 6 7 8 9
	 * 8 9 1 7 1 2 5 8 9 4
	 * 8 9 1 1 7 2 5 8 9 4
	 * 
	 * moveElement 3 4
	 * 0 1 2 3 4 5 6 7 8
	 * 9 8 7 6 5 4 3 2 1
	 * 9 8 7 5 6 4 3 2 1
	 * 
	 * moveElement 3 1
	 * 0 1 2 3 4 5 6 7 8 9
	 * 8 9 1 7 1 2 5 8 9 4
	 * 8 7 9 1 1 2 5 8 9 4
	 * 
	 * moveElement 1 5
	 * 0 1 2 3 4 5 6 7 8 9
	 * 8 9 1 7 1 2 5 8 9 4
	 * 8 1 7 1 2 9 5 8 9 4
	 * 
	 * 8 9 1 7 1 2 5 8 9 4 => 
	 * 
	 *  
	 * @param array
	 * @param elIdx
	 * @return
	 */
	public static int[] moveElement(int[] array, int elSrcIdx, int elDstIdx)
	{
		moveElement(IntArrayListAdapter.adapt(array), elSrcIdx, elDstIdx);
		return array;
	}
	
	public static List<Integer> moveElement(List<Integer> array, int elSrcIdx, int elDstIdx)
	{
		int elSrc = array.get(elSrcIdx);
		int step = (int)Math.signum(elDstIdx - elSrcIdx);
		
		int i = elSrcIdx;		
		while(i != elDstIdx)
		{
			array.set(i, array.get(i+step));
			i = i + step;
		}
		
		array.set(elDstIdx, elSrc);
		
		return array;
	}
	
	public static List<Pair<Integer, Integer>> createPairs(String... strings)
	{
		List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
		
		for (String string : strings)
		{
			String[] strPairs = string.split(":");
			Pair<Integer, Integer> p1 = new Pair<Integer, Integer>();
			
			try
			{
				if (strPairs.length > 0)
					p1.setFirst(Integer.parseInt(strPairs[0]));
			}
			catch (NumberFormatException e)
			{
			}
			
			try
			{
				if (strPairs.length > 1)
					p1.setSecond(Integer.parseInt(strPairs[0]));
			}
			catch (NumberFormatException e)
			{
			}
			
			l.add(p1);
		}
		
		return l;
	}
	
	public static boolean compareArrays(int[] a1, int[] a2)
	{
		if (a1 == null || a2 == null)
		{
			return a1 == a2;
		}
		
		if (a1.length != a2.length)
		{
			return false;
		}
		
		for (int i = 0; i < a2.length; i++)
		{
			if (a1[i] != a2[i])
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static boolean compareArrays(Object[] a1, Object[] a2)
	{
		if (a1 == null || a2 == null)
		{
			return a1 == a2;
		}
		
		if (a1.length != a2.length)
		{
			return false;
		}
		
		for (int i = 0; i < a2.length; i++)
		{
			if ((a1[i] == null && a2[i] != null) || !a1[i].equals(a2[i]))
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static boolean compareArrays(int[][] a1, int[][] a2){
		if (a1 == null || a2 == null)
		{
			return a1 == a2;
		}
		
		if (a1.length != a2.length)
		{
			return false;
		}
		
		for (int i = 0; i < a2.length; i++)
		{
			if (!compareArrays(a1[i], a2[i]))
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static boolean compareLists(List<Integer> l1, List<Integer> l2)
	{
		if (l1 == null || l2 == null)
		{
			return l1 == l2;
		}
		
		if (l1.size() != l2.size())
		{
			return false;
		}
		
		for (int i = 0; i < l1.size(); i++)
		{
			if (l1.get(i) != l2.get(i))
			{
				return false;
			}
		}
		
		return true;
	}
	
	public static int[] reverseArrayPart(int[] array, int from, int length)
	{
		for (int i = from; i < from + length / 2 ; ++i)
		{
			int tmp = array[i];
			array[i] = array[from + (length - 1)  - (i - from) ];
			array[from + (length - 1) - (i - from) ] = tmp;
		}
		
		return array;
	}
	
	public static int[] reverseArrayPartByIndexes(int[] array, int from, int to)
	{
		//([1 2 3 4 5], 1, 2 1 		
		//int idx = from + (to + 1 - from) / 2;		
		//([1 2 3 4 5], 1, 3 => i < 2
		if (from > to)
		{
			int t = from;
			from = to;
			to = t;
		}
		
		for (int i = from; i < from + (to + 1 - from) / 2 ; ++i)
		{
			int tmp = array[i];
			array[i] = array[to - (i - from) ];
			array[to - (i - from) ] = tmp;
		}
		
		return array;
	}
	
	public static boolean compare(List<Pair<Integer, Integer>> l1, List<Pair<Integer, Integer>> l2)
	{
		if (l1.size() != l2.size())
			return false;
		
		for (int i = 0; i < l1.size(); i++)
		{
			Pair<Integer, Integer> p1 = l1.get(i);
			Pair<Integer, Integer> p2 = l2.get(i);
			
			if (!p1.equals(p2))
				return false;
		}
		
		return true;
	}
	
	public static Set<Pair<Integer, Integer>> createSet(List<Pair<Integer, Integer>> l)
	{
		Set<Pair<Integer, Integer>> hashSet = new HashSet<Pair<Integer,Integer>>();
		
		for (Pair<Integer, Integer> pair : l)
		{
			hashSet.add(pair);
		}
		
		return hashSet;
	}
	
	public static int[] toPrimitiveArray(List<Integer> list)
	{
		int[] array = new int[list.size()];
		for (int i = 0; i < list.size(); i++)
		{
			array[i] = list.get(i);
		}
		
		return array;
	}
	
	public static String toBinaryString(int num)
	{
	    //01011000
	    //10100111
	    // x + ~x + 1 = 0
	    // -x = ~x + 1
        
		int mask = 1;
        
        String result = "";
        
        do
        {
            result = ((num & mask) != 0 ? "1" : "0") + result;
            mask = mask << 1;
        }
        while(mask != 0);
        
        return result;
	}
	
	public static String toBinaryString(long num)
	{
	    //01011000
	    //10100111
	    // x + ~x + 1 = 0
	    // -x = ~x + 1
        
		long mask = 1;
        
        String result = "";
        
        do
        {
            result = ((num & mask) != 0 ? "1" : "0") + result;
            mask = mask << 1;
        }
        while(mask != 0);
        
        return result;
	}
	
	public static void printBinary(int num)
	{
		System.out.println(toBinaryString(num));
	}
	
	public static int fromBinary(String strBinary)
	{
	    //1011
	    int j = 0;
	    int b = strBinary.charAt(j++) == '1'? 1 : 0;
	    
	    for( ; j < strBinary.length(); j++ )
        {
	        b = (strBinary.charAt(j) == '1'? 1 : 0) + (b << 1);
        }
	    
	    return b;
	}
	
	public static int random(int lower, int upper)
	{
	    double fLower =lower;
	    double fUpper =upper;
	    
	    fLower -= 0.5;
	    fUpper += 0.5;
	    
	    return (int)Math.round(Math.random()*(fUpper - fLower) + fLower);
	}

	public static <T> T getRandomListElem(List<T> elems) {
		return elems.get(Utils.random(0, elems.size() - 1));
	}
	
	public static double round(double value, double hint) {
		double scale = Math.pow(10, -getOrder(hint));
		if (scale == 0) {
			return Math.floor(value);
		}

		double wholePart = (double) ((int) value);
		double ratioPart = value - wholePart;
		double returnValue = wholePart
				+ ((double) ((int) (ratioPart * scale + (ratioPart < 0 ? -0.5
						: 0.5)))) / scale;
		return returnValue;
	}

	public static double getOrder(double value) {
		return round(Math.log10(value));
	}

	public static double round(double value) {
		return (long) (value + (value > 0 ? 0.5 : -0.5));
	}
	
	/**
	 * Creates a reversed 'view' of the input list. 
	 * @param l
	 * @return
	 */
	public static <E> List<E> reversedList(final List<E> l) {
		return new AbstractList<E>() {
			@Override
			public E get(int i) {
				return l.get(l.size() - i - 1);
			}

			@Override
			public int size() {
				return l.size();
			}
		};
	}
	
	public static <T> List<T> readFromFile(File f, String splitRegex, IConverter<String, T> c) throws IOException {
		List<T> l = new ArrayList<T>();
		try(BufferedReader br = new BufferedReader(new FileReader(f))){
			String line = null;
			while((line = br.readLine()) != null) {
				String[] parts = line.split(splitRegex);
				for (String p : parts) {
					T res = c.convert(p);
					l.add(res);
				}
			}
			return l;
		}
	}
	
	public static List<Object> readList(File f, char openBracket, char closeBracket) throws IOException {
		return readList(new FileInputStream(f), openBracket, closeBracket);
	}
	
	@SuppressWarnings("unchecked")
	public static List<Object> readList(InputStream s, char openBracket, char closeBracket) throws IOException {
		Deque<Object> stack = new ArrayDeque<>();
		
		List<Object> result = null;
		
		try(InputStreamReader reader = new InputStreamReader(s)){
			StreamTokenizer in = new StreamTokenizer(reader);
			boolean eof = false;
	         do {
	            int token = in.nextToken();
	            switch (token) {
	               case StreamTokenizer.TT_EOF:
	                  eof = true;
	                  break;
	               case StreamTokenizer.TT_NUMBER:
	               {
	            	   List<Object> l = (List<Object>) stack.peek();
	            	   l.add(in.nval);
	               }
	                  break;
	               default:
	            	   if (openBracket == (char)token) {
							List<Object> l = new ArrayList<>();
							stack.push(l);
						}
						else if (closeBracket == (char)token) {
							List<Object> l = (List<Object>) stack.pop();
							List<Object> parent = (List<Object>) stack.peek();
							if (parent != null){
								parent.add(l);
							}
							else {
								result = l;
								eof = true;
							}
							
						}
	            }
	         } while (!eof);
		}
		
		return result;
	}
	
	public static int[][] listTo2dArray(List<Object> ll) {
		int[][] arr = new int[ll.size()][];
		for (int i = 0; i < ll.size(); i++) {
			@SuppressWarnings("rawtypes")
			List l = (List) ll.get(i);
			arr[i] = new int[l.size()];
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = ((Number) l.get(j)).intValue();
			}
		}
		return arr;
	}
	
	public static int C_n_k(int n, int k) {
		int[][] C_n_k = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			C_n_k[i][0] = 1;
		}
		for (int i = 1; i <= n; i++) {
			C_n_k[i][i] = 1;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				C_n_k[i][j] = C_n_k[i - 1][j - 1]  + C_n_k[i - 1][j];
				if (i == n && j == k) {
					return C_n_k[i][j];
				}
			}
		}
		return C_n_k[n][k];
	}
	
	public static void cyclicShiftRight(int[] seq) {
    	int prev = seq[0];
    	for (int i = 0; i < seq.length; i++) {
    		int j = (i + 1) % seq.length;
			int t = seq[j]; 
			seq[j] = prev;
			prev = t;
		}
    }
	
	private Utils(){
	}
}